'''
在列表中查找元素，如果列表中有该元素，打印找到了，如果列表中没有该元素，打印没找到
list1= [51,31,16,2,45,23,45,7]   5
顺序查找：按照列表的存储顺序，逐个查找
        缺点：可能需要全部遍历查找，效率慢

二分查找：优点：查找效率高
        前提：列表的元素是按照顺序排序的
2 7 16 23 31 45 45 51    11
'''
list1= [51,31,16,2,45,23,45,7]
def search(l,key):
    for i in range(len(l)):
        if l[i] == key:
            return f"找到了,下标为：{i}"

    return "没找到"

print(search(list1,51))


"""
list2=3,4,11,24,35,38,41,46,55   key=46
                min(35<key)
list2=38,41,46,55            key=46
        min(min<key)       
list2=  46,55               key=46
        min  ---找到了

            

list2=3,4,11,24,35,38,41,46,55   key=5
                min(35>key)
list2=3,4,11,24               key=5
        min(min<key)
list2= 11,24      key=5
       min(min>key)
list2=[]       为空，则没找到

"""
def binary_search(l,key):
    if len(l)==0:
        return "没找到"
    # 获取中间下标
    min = len(l)//2
    # 获取中间值和key比较
    # min值>key  往前找
    if l[min]>key:
        return binary_search(l[:min:],key)
    # min值<key  往后找
    elif l[min]<key:
        return binary_search(l[min+1::], key)
    # min值=key  结束 return "找到了"
    else:
        return "找到了"
list2 =[3,4,11,24,35,38,41,46,55]
print(binary_search(list2,51))


"""
二分查找：
list2=3, 4, 11, 24, 35, 38, 41, 46, 55   key=46
      l             min              r
                        l   min      r
                                 l=minr
                        
list2=3, 4, 11, 24, 35, 38, 41, 46, 55   key=5
      l             min             r
      l  min     r
             l=minr
             r<l              ---没找到
"""
def binary_search1(list1,key):
    # 定义三个变量
    l = 0
    r = len(list1)-1  #8

    while l <= r:
        min = (l + r) // 2
        # min对应的元素和key比较
        # min>key  改变r的值
        if list1[min]>key:
            r = min-1
        # min<key  改变l的值
        elif list1[min]<key:
            l = min+1
        # min=key  找到了
        elif list1[min] == key:
            return "找到了"

    return "没找到"

print(binary_search1(list2,35))






